package leetcode_500;

import java.util.Arrays;
import java.util.Comparator;

import helpclass.Interval;



/**
 * Non_OverlappingIntervals_435 给定一个区间数组 求最小移除多少个区间 剩下区间都没有重叠空间
 * 2018年8月17日 上午10:53:31
 * @author 周杨
 * describe :用贪心算法 先按活动结束时间排序 然后我们的策略是 尽量保留上一次活动的结束时间 AC 78%
 * see:https://www.cnblogs.com/liujinhong/p/6399198.html
 */
public class Non_OverlappingIntervals_435_ {
	
	
	public int eraseOverlapIntervals(Interval[] intervals) {
        Arrays.sort(intervals, new Comparator<Interval>() {
			@Override
			public int compare(Interval o1, Interval o2) {
				if(o1.end>o2.end)
					return 1;
				if(o1.end<o2.end)
					return -1;
				return 0;
			}
		});
        int res=0,end=intervals[0].end;
        for(int i=1;i<intervals.length;++i){
        	if(intervals[i].end==end)
        		++res;
        	else if(intervals[i].start<end)
        		++res;
        	else//可以并存 调整end
        		end=intervals[i].end;
        		
        }
        return res;
    }
}
